package leetcode;

public class LeetCodeMain101 {
    public int cuttingRope1(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        dp[2]=1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i]=Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }
    public int cuttingRope(int n) {
        if (n<4){
            return n-1;
        }
        long res=1;
        while (n>4){
            res=(res*3)%1000000007;
            n-=3;
        }
        return (int)(res*n%1000000007);
    }
    public int hammingWeight(int n) {
        int count=0;
        while (n!=0){
            count++;
            n=n&(n-1);
        }
        return count;
    }

    public double myPow(double x, int n) {
        long sum=n;
        return sum>=0?num(x,sum):1/num(x,-sum);
    }

    public double num(double x, long n) {
        if (n==0){
            return 1.0;
        }
        double sum=num(x, n/2);
        return n%2==0?sum*sum:sum*sum*x;
    }
    public ListNode deleteNode(ListNode head, int val) {
        ListNode node=new ListNode(-1);
        ListNode node1=node;
        node.next=head;
        while (node1.next.val!=val){
            node1=node1.next;
        }
        node1.next=node1.next.next;
        return node.next;
    }
}
